package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._101_Symmetric_Tree.TreeNode;

import util.LogUtils;

/*
 * 
原题

　　Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. 
　　For example, 
　　"A man, a plan, a canal: Panama" is a palindrome. 
　　"race a car" is not a palindrome. 
　　Note: 
　　Have you consider that the string might be empty? This is a good question to ask during an interview. 
　　For the purpose of this problem, we define empty string as valid palindrome. 

题目大意

　　给定一个字符串，判断它是否是回文字符串，仅考虑字母，并且忽略大小写。 

解题思路

　　使用首尾指针，分别找到第一个符合条件的位置，进行比较，如果相等就进行下一组比较，不相等就返回false，直到所有的字母都处理完。
	采用二分法，一个指针从左边遍历，一个从右边遍历，跳过非字母和非数字，当遍历到中点依然相同那就是回文
 * @Date 2017-09-14 10：54
 */
public class _125_Valid_Palindrome {
	
    public boolean isPalindrome(String s) {
    	if (s==null)					return false;
    	if (s.length() == 0)			return true;
    	int i = 0, j = s.length()-1;
    	
    	while (i < j) {
        	if (!isAlphanumeric(s.charAt(i))) {
        		i++;
        		continue;
        	}
        	if (!isAlphanumeric(s.charAt(j))) {
        		j--;									//忽略非英文字母的字符
        		continue;
        	}
    		if (!isEqual(s.charAt(i), s.charAt(j)))	return false;
    		i++;
    		j--;
    	}
        return true;
    }
    /** 
     * 判断是否是字母或数字 
     *  
     * @param char character 
     * @return boolean true(is alphanumeric) / false(is not alphanumeric) 
     */  
    public boolean isAlphanumeric(char c) {  
        if ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')) {  
            return true;  
        }  
        return false;  
    }  
    /**
     * 忽略大小写：将两个字符统一转换为小写(统一转换为大写也可以)
     * @param ch1
     * @param ch2
     * @return
     */
    private boolean isEqual(Character ch1, Character ch2) {
    	if (ch1.toLowerCase(ch1) == ch2.toLowerCase(ch2))	
    		return true;
    	return false;
    }
	
	
	public static void main(String[] args) {
		_125_Valid_Palindrome obj = new _125_Valid_Palindrome();
		LogUtils.println("结果", 
				obj.isPalindrome(
						"}})))"
				));
		LogUtils.println("结果", 
				Character.isLetter(" ".charAt(0)));
	}

}
